// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

// bucketSort 是一个函数，它将 float64 数组和 bucketSize 作为输入并返回排序后的 float64 数组
func bucketSort(array []float64, bucketSize int) []float64 {

	// 初始化变量以保存数组中的最大值和最小值
	var max, min float64

	// 遍历数组以找到最大值和最小值
	for _, n := range array {
		if n < min {
			min = n
		}
		if n > max {
			max = n
		}
	}

	// 计算所需的桶数并将桶创建为切片
	nBuckets := int(max-min)/bucketSize + 1
	buckets := make([][]float64, nBuckets)
	for i := 0; i < nBuckets; i++ {
		buckets[i] = make([]float64, 0)
	}

	// 根据值将数组的元素分配到各自的桶中
	for _, n := range array {
		idx := int(n-min) / bucketSize
		buckets[idx] = append(buckets[idx], n)
	}

	// 使用插入排序对每个桶中的元素进行排序，并将排序后的桶连接起来形成排序数组
	sorted := make([]float64, 0)
	for _, bucket := range buckets {
		if len(bucket) > 0 {
			insertionSort(bucket)
			sorted = append(sorted, bucket...)
		}
	}

	// 返回排序后的数组
	return sorted
}

// insertionSort 是一个函数，它接受一个 float64 数组，并使用插入排序算法将其按升序排序
func insertionSort(array []float64) {
	for i := 0; i < len(array); i++ {
		// 从数组的未排序部分中选择一个元素，并将其插入到已排序部分的正确位置
		temp := array[i]
		j := i - 1
		for ; j >= 0 && array[j] > temp; j-- {
			array[j+1] = array[j]
		}
		array[j+1] = temp
	}
}

func main() {
	array := []float64{33, 23, 56, 7, 8, 18, 99, 28}
	res := bucketSort(array, 5)
	fmt.Println(res)
}

//$ go run bucketSort.go
//[7 8 18 23 28 33 56 99]
